// 2025/10/02
// Author: Forever
#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<pair<int, int>> edges[3001];
int n, m, h[3001], dist[3001], cnt[3001];
bool inq[3001];
const long long INF = 4e18;


void dijistra(int s)
{
    for (int i = 0; i <= n; i++) dist[i] = INF;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        int d = pq.top().first, v = pq.top().second;
        pq.pop();
        if (dist[v] < d)
            continue;
        for (auto x : edges[v]) {
            int a = x.first, w = x.second;
            if (dist[a] > dist[v] + w) {
                dist[a] = dist[v] + w;
                pq.push({dist[a], a});
            }
        }
    }
}

bool spfa(int s)
{
    for (int i = 0; i <= n; i++) {
        h[i] = INF;
        cnt[i] = 0;
        inq[i] = false;
    }
    h[s] = 0;
    inq[s] = true;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (auto ed : edges[u]) {
            int v = ed.first, w = ed.second;
            if (h[v] > h[u] + w) {
                h[v] = h[u] + w;
                if (!inq[v]) {
                    q.push(v);
                    inq[v] = true;
                    ++cnt[v];
                    if (cnt[v] > n)
                        return false;
                }
            }
        }
    }
    return true;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[u].push_back({ v, w });
    }
    for (int i = 1; i <= n; i++)
        edges[0].push_back({ i, 0 });
    if (!spfa(0)) {
        cout << -1;
        return 0;
    }
    for (int i = 1; i <= n; i++)
        for (auto& x : edges[i])
            x.second += h[i] - h[x.first];
    for (int i = 1; i <= n; i++){
        dijistra(i);
        long long ans = 0;
        for (int j = 1; j <= n; j++) {
            long long val = dist[j] - h[i] + h[j];
            if (val >= INF / 2) val = 1000000000;
            ans += val * j;
        }
        cout << ans << endl;
    }
    return 0;
}